|
In the theory of formal languages, the Myhill–Nerode theorem provides a necessary and sufficient condition for a language to be regular. The theorem is named for John Myhill and Anil Nerode, who proved it at the University of Chicago in 1958 . ==Statement of the theorem== Given a language ''L'', and a pair of strings ''x'' and ''y'', define a distinguishing extension to be a string ''z'' such that exactly one of the two strings ''xz'' and ''yz'' belongs to ''L''. Define a relation ''RL'' on strings by the rule that ''x RL y'' if there is no distinguishing extension for ''x'' and ''y''. It is easy to show that ''RL'' is an equivalence relation on strings, and thus it divides the set of all strings into equivalence classes. The Myhill–Nerode theorem states that ''L'' is regular if and only if ''RL'' has a finite number of equivalence classes, and moreover that the number of states in the smallest deterministic finite automaton (DFA) recognizing ''L'' is equal to the number of equivalence classes in ''RL''. In particular, this implies that there is a unique minimal DFA with minimum number of states. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Myhill–Nerode theorem」の詳細全文を読む スポンサード リンク
|